
#include "trap.h"
int trapBrute(std::vector<int> &height) {
    const int n = height.size();
    int left, right, left_height, right_height;
    int max_value = 0;
    for (int i = 1; i < n - 1; i++) {
        left = i;
        right = i;
        left_height = height[i];
        for (int j = i; j >= 0; j--) {
            if (height[j] > left_height) {
                left_height = height[j];
                left = j;
            }
        }
        right_height = height[i];
        for (int j = i; j < n; j++) {
            if (height[j] > right_height) {
                right_height = height[j];
                right = j;
            }
        }
        max_value += (std::min(right_height, left_height) - height[i]);
    }
    return max_value;
}

int trap(std::vector<int> &height) {
    std::stack<int> s;
    int result = 0;
    int current_index = 0;
    int left = 0;
    for (int i = 0; i < height.size(); i++) {
        while (!s.empty() && height[i] > height[s.top()]) {
            current_index = s.top();
            s.pop();
            if (s.empty())
                break;
            left = s.top();
            result += (i - left - 1) * (std::min(height[i], height[left]) -
                                        height[current_index]);
        }
        s.push(i);
    }
    return result;
}
